//Given a non-negative integer x, compute and return the square root of x. 
//
// Since the return type is an integer, the decimal digits are truncated, and on
//ly the integer part of the result is returned. 
//
// 
// Example 1: 
//
// 
//Input: x = 4
//Output: 2
// 
//
// Example 2: 
//
// 
//Input: x = 8
//Output: 2
//Explanation: The square root of 8 is 2.82842..., and since the decimal part is
// truncated, 2 is returned. 
//
// 
// Constraints: 
//
// 
// 0 <= x <= 231 - 1 
// 
// Related Topics 数学 二分查找 
// 👍 675 👎 0


package leetcode.editor.cn;

//Java：Sqrt(x)
class P69Sqrtx {
    public static void main(String[] args) {
        Solution solution = new P69Sqrtx().new Solution();
        // TO TEST
        System.out.println(Integer.MAX_VALUE);

        System.out.println(solution.mySqrt(183692038));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int mySqrt(int x) {
            if (x == 0 || x == 1) {
                return x;
            }
            int left = 1;
            int right = x;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (mid >= 46340) {
                    mid = 46340;
                    left = 0;
                    right = 46340;
                }
                int val = mid * mid;
                if (val == x) {
                    return mid;
                } else if (val > x) {
                    right = mid - 1;
                } else if (val < x) {
                    left = mid + 1;
                }
            }
            return right;
        }
        public  int mySqrtAnother(int x) {
            if (0 <= x && x < 1) {
                return 0;
            } else if (x == 1) {
                return 1;
            }
            int temp = x;
            int count = 0;
            long max = 1;
            long min = 1;

            while (temp != 0) {
                if (count == 0) {
                    min = 1;
                    max = 10;
                    temp = temp / 10;
                    count++;
                    continue;
                } else if (count % 2 == 0) {
                    max = max * 10;

                }
                if (count % 3 == 0) {
                    min = min * 10;
                }
                count++;
                temp = temp / 10;
            }
            long middle = 0;
            while (min <= max) {
                middle = (min + max) / 2;
                if (middle * middle == x || (middle * middle < x) && ((middle + 1) * (middle + 1)) > x) {
                    return (int) middle;
                } else if (middle * middle < x) {
                    min = middle + 1;
                } else {
                    max = middle - 1;
                }

            }
            return 0;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}